#include "copycat.h"
#include "define.h"

CTree::CTree()
{
}

CTree::~CTree()
{
}

bool CTree::Init()
{
	num_node = 0;
	for( int i=0; i<NUM_MAX_NODE; i++ )	{
		node[i].Init();
	}
}

int find_first_EB( CUStringList &ls )
{
	for( int i=0; i<ls.GetSize(); i++ )	{
		if( strcmp( ls.GetAt(i), ")" ) == 0 )	return i;
	}
	return -1;
}

int find_left_BB( CUStringList &ls, int eb )
{
	for( int i = eb; i>=0; i-- )	{
		if( strcmp( ls.GetAt(i), "(" ) == 0 )	return i;
	}
	return -1;
}

void numbering( CUStringList &ls )
{
	int curr_level = 0;
	char buff[12];
	for( int i=0; i<ls.GetSize(); i++ )	{
		CUString label = ls.GetAt(i);
		if( label == "(" )	{
			sprintf( buff, "(@%d", curr_level );
			curr_level++;
			ls.SetAt(i, buff );
		}
		else if( label == ")" )	{
			curr_level--;
			sprintf( buff, ")@%d", curr_level );
			ls.SetAt(i, buff );
		}


		fprintf( stdout, "%s ", ls.GetAt(i) );
	}
	fprintf( stdout, "\n" );
}


bool CTree::LoadTree( CUString str )
{
	if( str.Find( "O\t" ) == 0 )	{
		str = str.Mid(2);
	}
	else if( str.Find("X\t") == 0 )	{
		return false;
	}

	str.Replace(" ()", " -LRB-)");
	str.Replace(" ))", " -RRB-)");

	if( str.Count( "(" ) != str.Count(")" ) )	{
		return false;
	}

//	fprintf( stderr, "%s\n\n", str.GetStr() );
	str.Replace( "(", " ( " );
	str.Replace( ")", " ) " );


	Init();
	int st[1000];
	int s=-1;

	CUStringList ls;
	ls.TokenizeByChar( str, " ", false );

	int last_idx = -1;

	for( int i=0; i<ls.GetSize(); i++ )	{
		CUString label = ls.GetAt(i);

		if( label == "(" )	{
			s++;
			st[s] = last_idx;
		}
		else if ( label == ")" )	{
			last_idx = st[s];
			s--;
		}
		else 	{

//			label.Replace( "\\/", "#SLASH#" );
			if( num_node + 4 > NUM_MAX_NODE )	{
				fprintf( stderr, "exceed max node num %d\n", num_node );
				return false;
			}

			node[num_node].label = label;
			node[num_node].label.Replace( "-LRB-", "(" );
			node[num_node].label.Replace( "-RRB-", ")" );
			node[num_node].id = num_node;

			// root
			if( last_idx == -1 )	{
				node[num_node].level = 0;
			}
			// non-root
			else	{
				node[num_node].parent = last_idx;
				CNode &parent = node[last_idx];

				if( parent.num_child+1  > NUM_MAX_CHILD )	{
					fprintf( stderr, "exceed max child num %d\n", parent.num_child );
					return false;
				}

				parent.child[parent.num_child] = num_node;
				parent.num_child++;
				node[num_node].level = parent.level+1;
			}

			last_idx = num_node;
			num_node++;
		}
	}

/*
	for( int i=0; i<num_node; i++ )	{
		CNode &n = node[i];
		if( n.num_child != 0  )	continue;

		CUString label = n.label;
		int cnt = label.Count("/");

		if( cnt == 0 )	{
			continue;
		}
		else if( cnt == 1 )	{
			n.label = label.Left( label.Find("/") );
		}
		else	{
			fprintf( stdout, "\nERROR %s \t %d\n", label.GetStr(), label.Count("/")  );
		}
	}
*/

	//Print();



	/*
	numbering( ls );
	int curr_level = 0;
	char buff[12];
	for( int i=0; i<ls.GetSize(); i++ )	{
		CUString label = ls.GetAt(i);
		if( label.Find( "(@" ) == 0  )	{
			CUStringList ls2( label, "@" );
			int level = atoi( ls2.GetAt(1) );
			i++;
			label = ls.GetAt(i);
			fprintf( stdout, "%s(%d) ", label.GetStr() , level );
		}
		else	{
		fprintf( stdout, "%s ", ls.GetAt(i) );
		}
	}
	*/


	/*
	while(1)	{
		int i = find_first_EB( ls );
		if( i<0 )	break;

		int j = find_left_BB( ls, i );
		if( j<0 )	break;

		ls.SetAt( i, "]" );
		ls.SetAt( j, "[" );
		for( int i=0; i<ls.GetSize(); i++ )	{
			fprintf( stdout, "%s ", ls.GetAt(i) );
		}
		fprintf( stdout, "\n" );
	}
	*/



	/*
	int level_stack[NUM_MAX_NODE];
	int level_stack_num=0;
	int curr_stack=0;
	for( int i=0; i<ls.GetSize(); i++ )	{

		CUString label = ls.GetAt(i);
		if( label == "(" )	{
			i++;
			label = ls.GetAt(i);
			curr_stack++;
			num_node++;
			
			fprintf( stdout, "Load Nod-term: %s level(%d)\n", label.GetStr(), curr_stack );
		}
		else if( label == ")" )	{
			curr_stack--;
		}
		else	{
			curr_stack++;
			num_node++;

			fprintf( stdout, "Load Term: %s level(%d)\n", label.GetStr(), curr_stack );
		}


//		fprintf( stdout, "%s ", ls.GetAt(i) );

	}
	*/

//	fprintf( stdout, "\n" );
	return true;
}

void CTree::Print()
{
	for( int i=0; i<num_node; i++ )	{
		fprintf( stdout, "[%2d] %10s LV:%2d PAR:%2d CH:%d ", i, node[i].label.GetStr(), node[i].level, node[i].parent, node[i].num_child );

		if( node[i].span_from == NULL_NUM )	{
			fprintf( stdout, " (  ) " );
		}
		else	{
			fprintf( stdout, " (%d~%d) ", node[i].span_from, node[i].span_to );
		}


		fprintf( stdout, "[ " );
		for( int j=0; j<node[i].num_child; j++ )	{
			fprintf( stdout, "%d ", node[i].child[j] );
		}
		fprintf( stdout, "]\n" );
	}


}

void CTree::PrintParse2File( CUTextFile &file )
{
	CUString res;
	PrintStrRecurr( 0, res );
	res.Trim(" ");
	fprintf( file.GetFP(), "%s\n", res.GetStr() );

//	fprintf( file.GetFP(), "node: %d\n", num_node );
}

void CTree::PrintLex2File( CUTextFile &file )
{
	int ls[NUM_MAX_NODE];
	int s=-1;

	int num_print = 0;
	GetTraverseList( ls, s, ROOT_ID );
	for( int i=0; i<s; i++ )	{
		int idx = ls[i];
		if( node[idx].IsTerminal() == false )	continue;

		if( num_print != 0 )	fprintf( file.GetFP(), " " );
		fprintf( file.GetFP(), "%s", node[idx].label.GetStr() );
		num_print++;
	}
	fprintf( file.GetFP(), "\n" );
}


void CTree::PrintLexPos2File( CUTextFile &file )
{
	int ls[NUM_MAX_NODE];
	int s=-1;

	GetTraverseList( ls, s, ROOT_ID );
	int num_print = 0;
	for( int i=0; i<s; i++ )	{
		int idx = ls[i];
		if( node[idx].IsTerminal() == false )	continue;

		int pid = node[idx].parent;
		CUString pos = node[pid].label;

		if( num_print != 0 )	fprintf( file.GetFP(), " " );
		fprintf( file.GetFP(), "%s/%s", node[idx].label.GetStr(), pos.GetStr() );
		num_print++;
	}
	fprintf( file.GetFP(), "\n" );
}

void CTree::PrintReordInfo2File( CUTextFile &file )
{
	int ls[NUM_MAX_NODE];
	int s=-1;

	int num_print = 0;
	GetTraverseList( ls, s, 0 );
	for( int i=0; i<s; i++ )	{
		int idx = ls[i];
		if( node[idx].IsTerminal() == false )	continue;


		if( num_print != 0 )	fprintf( file.GetFP(), " " );
		//fprintf( file.GetFP(), "%s-%d", node[idx].label.GetStr(), idx );
		fprintf( file.GetFP(), "%d", idx );
		num_print++;
	}
	fprintf( file.GetFP(), "\n" );
}


void CTree::PrintStrRecurr( int curr_node, CUString &res )
{
	CNode n = node[curr_node ];
	if( n.num_child == 0 )	{
			res += CUString(" ") + n.label;
	}
	else	{
		res += CUString(" (") + n.label;
		for( int i=0; i<n.num_child; i++ )	{
			PrintStrRecurr( n.child[i], res );
		}
		res +=  CUString(")" );
	}
	res.Trim(" ");
}

/*
void CCopycat::CTree::PrintStr()
{
	CUString str;
	int st[NUM_MAX_NODE];
	int num=0;
	st[num] = 0;

	while( num >= 0 )	{
		int id = st[num];
		num--;

		CNode n = node[id];

		if( n.num_child == 0 )	{
			str +=  n.label;
		}
		else	{

			str += CUString("(") + n.label;
			for( int i=n.num_child-1; i>=0;  i-- )	{
				num++;
				st[num] = n.child[i];
			}
			str +=  CUString(")" );
		}

	}

	fprintf( stdout, "%s\n", str.GetStr() );

}
*/


/////////////////////////////////////////////////////////////////
void CTree::GetTraverseList( int ls[], int &s, int start_id )
{
	s=0;

	int st[NUM_MAX_NODE];
	int m = 0;
	st[m] = start_id;

	while( m >= 0 )	{
		int id = st[m--];
		ls[s++] = id;

		for( int i=node[id].num_child-1; i>=0; i-- )	{
			st[++m] = node[id].child[i];
		}
	}
}


/////////////////////////////////////////////////////////////////
void CTree::GetLexNodeList( int ls[], int &s, int start_id )
{
	s=0;

	int st[NUM_MAX_NODE];
	int m = 0;
	st[m] = start_id;

	while( m >= 0 )	{
		int id = st[m--];
		CNode &n = node[id];
		if( n.IsTerminal() == true )	{
			ls[s++] = id;
		}

//		for( int i=0; i<node[id].num_child; i++ )	{
		for( int i=node[id].num_child-1; i>=0; i-- )	{
			st[++m] = node[id].child[i];
		}
	}
}

//////////////////////////////////////////////////////////////////////////////
void CTree::UpdateSpan()
{
	int ls[NUM_MAX_NODE];
	int s=-1;
	GetTraverseList( ls, s, ROOT_ID );

	for( int i=0; i<s; i++ )	{
		CNode &n = node[i];
		if( n.span_from == NULL_NUM )	continue;

		int sid = i;
		while( 1 )	{
			int pid = node[sid].parent;
			if( pid == NULL_NUM )	break;

			CNode &p = node[pid];
			CNode &c = node[sid];

			if( p.span_from == NULL_NUM )	{
				p.span_from = c.span_from;
				p.span_to   = c.span_to;
			}
			else	{
				if( c.span_from < p.span_from )	p.span_from = c.span_from;
				if( p.span_to   < c.span_to   )	p.span_to   = c.span_to;
			}

			sid = pid;
			
		}
	}
}

//////////////////////////////////////////////////////////////////////////////
void CTree::UpdateTgtAlign()
{
	int ls[NUM_MAX_NODE];
	int s=-1;
	GetLexNodeList( ls, s, ROOT_ID );

	for( int i=0; i<s; i++ )	{
		int curr_idx = ls[i];
		CNode &curr = node[ curr_idx ];
		if( curr.num_tok_aligns == 0 )	continue;
//		fprintf( stdout , "%s\n", curr.label.GetStr() );

		int traverse_id = curr_idx;
		while( 1 )	{
			int pid = node[traverse_id].parent;
			if( pid == NULL_NUM )	break;

			CNode &p = node[pid];
			CNode &trav = node[traverse_id];

//		fprintf( stdout , " %s->%s\n", trav.label.GetStr(), p.label.GetStr()  );
			for( int j=0; j<trav.num_tok_aligns; j++ )	{
				p.AddAlign( trav.tok_aligns_tgt[j] );
			}

			traverse_id = pid;
			
		}
	}
}


//////////////////////////////////////////////////////////////////////////////
int CTree::Lex2Node( int lex_id )
{
	int ls[NUM_MAX_NODE];
	int s=-1;

	int curr_id = 0;
	GetTraverseList( ls, s, ROOT_ID );
	for( int i=0; i<s; i++ )	{
		int id = ls[i];
		CNode &n = node[id];
		if( n.IsTerminal() )	{
			curr_id++;
			if( curr_id == lex_id )	return id;
		}
	}

	return -1;
}

//////////////////////////////////////////////////////////////////////////////
CNode* CTree::GetNodeByLexID( int lex_id )
{
	int ls[NUM_MAX_NODE];
	int s=-1;

	int curr_id = 0;
	GetTraverseList( ls, s, ROOT_ID );
	for( int i=0; i<s; i++ )	{
		int id = ls[i];
		CNode &n = node[id];
		if( n.IsTerminal() )	{
			if( curr_id == lex_id )	return &(node[id]);
			curr_id++;
		}
	}

	return NULL;
}

//////////////////////////////////////////////////////////////////////////////
void CTree::ClearCross()
{
	for( int i=0; i<num_node; i++ )	{
		CNode &n = node[i];
		if( n.IsTerminal() )	{
			n.num_cross=0;
			continue;
		}

		n.num_cross = 0;
		n.num_tok_aligns = 0;
	}
}


//////////////////////////////////////////////////////////////////////////////
void CTree::UpdateCross()
{
	ClearCross();

	int ls[NUM_MAX_NODE];
	int s = -1;
	GetLexNodeList( ls, s, ROOT_ID );
	for( int i=0; i<s; i++ )	{
		int curr_id = ls[i];
	
		while(1)	{
			int pid = node[curr_id].parent;
			if( pid == NULL_NUM )	break;

			CNode &p = node[pid];
			CNode &c = node[curr_id];

			for( int j=0; j<c.num_tok_aligns; j++ )	{
				p.AddAlign( c.tok_aligns_tgt[j] );
			}

			curr_id = pid;
		}

	}

	for( int i=0; i<num_node; i++ )	{
		CNode &n = node[i];

		for( int j=0; j<n.num_tok_aligns; j++ )	{
			for( int k=0; k<n.num_tok_aligns; k++ )	{
				if( j==k )	continue;

				if( j<k && n.tok_aligns_tgt[j] > n.tok_aligns_tgt[k] )	{
					n.num_cross++;
					break;
				}
				if( j>k && n.tok_aligns_tgt[j] < n.tok_aligns_tgt[k] )	{
					n.num_cross++;
					break;
				}

			}
		}



	}
}

void CTree::Dump( FILE *fp )
{
	int ls[NUM_MAX_NODE];
	int s=-1;

	GetTraverseList( ls, s, ROOT_ID );
	int num_print = 0;
	for( int i=0; i<s; i++ )	{
		int idx = ls[i];
		CNode &n = node[idx];

		fprintf( fp, "%s (%d~%d) [", n.label.GetStr(), n.span_from, n.span_to );
		for( int j=0; j<n.num_tok_aligns; j++ )	{
			fprintf( fp, " %d ", n.tok_aligns_tgt[j] );
		}
		fprintf( fp, "]\n" );



		/*
		if( num_print != 0 )	fprintf( fp, " " );
		fprintf( fp, "%s/%s", node[idx].label.GetStr(), pos.GetStr() );
		num_print++;
		*/
	}
	fprintf( fp, "\n" );
}


void CTree::ReorderWA()
{
	int ls[NUM_MAX_NODE];
	int s=-1;

	GetTraverseList( ls, s, ROOT_ID );
	for( int i=0; i<s; i++ )	{
		int idx = ls[i];
		CNode &n = node[idx];

		if( n.num_child < 2 )	continue;
		bool have_null_align = false;
		for( int j=0; j<n.num_child; j++ )	{
			int cidx = n.child[j];
			CNode &c = node[cidx];
			if( c.span_from == NULL_NUM || c.span_to   == NULL_NUM )	{
				have_null_align = true;
				break;
			}
		}
		if( have_null_align == true )	{
//			n.label += "?";
			for( int j=0; j<n.num_child; j++ )	{
				char buf[1024];
				sprintf( buf, "[%d~%d]", node[ n.child[j] ].span_from, node[ n.child[j] ].span_to );
//				n.label += buf;
			}
			continue;
		}

		while( 1 )	{
			bool changed = false;
			for( int j=0; j<n.num_child-1; j++ )	{
				for( int k=j+1; k<n.num_child; k++ )	{

					int idx1 = n.child[j]; CNode &c1 = node[idx1];
					int idx2 = n.child[k]; CNode &c2 = node[idx2];
					if( c2.span_from < c1.span_from )	{
//						n.label += "*";

						n.child[j] = idx2;
						n.child[k] = idx1;
						changed = true;
						break;
						//					fprintf( stderr, "reordered %s [%s] [%s]\n", n.label.GetStr(), c1.label.GetStr(), c2.label.GetStr() );
					}
				}
				if( changed == true )	break;
			}

			if( changed == false )	break;
		}


		/*
		if( n.label.Find( "NP" ) == 0 && n.num_child == 2 )	{
			CNode &c1 = node[ n.child[0] ];
			CNode &c2 = node[ n.child[1] ];
			if( c1.label.Find("NP") == 0 || c2.label.Find("PP") == 0 )	{
				CUString str;
				PrintStrRecurr( i, str ); str.Trim(" ");
				fprintf( stdout, "###\n%s\n###\n", str.GetStr() );
				
			}
			else if( c2.label.Find("NP") == 0 || c1.label.Find("PP") == 0 )	{
				CUString str;
				PrintStrRecurr( i, str ); str.Trim(" ");
				fprintf( stdout, "###\n%s\n###\n", str.GetStr() );
			}
		}
		*/


		/*
		fprintf( fp, "%s (%d~%d) [", n.label.GetStr(), n.span_from, n.span_to );
		for( int j=0; j<n.num_tok_aligns; j++ )	{
			fprintf( fp, " %d ", n.tok_aligns_tgt[j] );
		}
		fprintf( fp, "]\n" );
		*/



		/*
		if( num_print != 0 )	fprintf( fp, " " );
		fprintf( fp, "%s/%s", node[idx].label.GetStr(), pos.GetStr() );
		num_print++;
		*/
	}

}



